<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>BFS二叉树遍历</title>
    <script src="https://d3js.org/d3.v7.min.js"></script>
    <style>
        .node {
            fill: lightblue;
            stroke: black;
            stroke-width: 1.5px;
            cursor: pointer;
        }

        .link {
            fill: none;
            stroke: #ccc;
            stroke-width: 2px;
        }

        .clicked {
            fill: orange;
        }

        .error {
            fill: red;
        }

        #message {
            font-size: 20px;
            font-weight: bold;
            margin-top: 20px;
        }

        #path {
            font-size: 16px;
            font-weight: bold;
            margin-top: 10px;
        }
    </style>
</head>
<body>
    <h1>BFS二叉树遍历</h1>
    <svg width="600" height="400"></svg>
    <div id="message"></div>
    <div id="path">正确路径：<span id="correct-path"></span></div>

    <script>
        // Function to randomly generate a binary tree with at least 5 nodes and depth up to 4
        let availableNumbers = Array.from({ length: 30 }, (_, i) => i + 1); // Array from 1 to 99

        function generateRandomTree(depth, maxChildren = 2, currentDepth = 0, minNodes = 5) {
            if (currentDepth >= depth || minNodes <= 0) return null;

            const randomIndex = Math.floor(Math.random() * availableNumbers.length);
            const nodeName = availableNumbers.splice(randomIndex, 1)[0];

            const children = [];
            const numChildren = Math.floor(Math.random() * (maxChildren + 1));

            for (let i = 0; i < numChildren; i++) {
                const childNode = generateRandomTree(depth, maxChildren, currentDepth + 1, minNodes - 1);
                if (childNode) {
                    children.push(childNode);
                }
            }

            return {
                name: nodeName,
                children: children.length > 0 ? children : null,
            };
        }

        // Generate a random binary tree with depth 4
        let treeData = generateRandomTree(4, 2, 0, 5);

        // BFS traversal sequence
        const correctBFSSequence = [];
        function bfs(root) {
            const queue = [root];
            while (queue.length > 0) {
                const node = queue.shift();
                correctBFSSequence.push(node.name);
                if (node.children) {
                    node.children.forEach(child => queue.push(child));
                }
            }
        }

        // Compute BFS sequence
        bfs(treeData);

        // Display the correct BFS sequence on the page
        document.getElementById("correct-path").innerText = correctBFSSequence.join(" -> ");

        let userClickIndex = 0;

        // Set up the SVG canvas dimensions
        const width = 600;
        const height = 400;

        const svg = d3.select("svg");

        // Create a tree layout
        const treeLayout = d3.tree().size([width - 100, height - 100]);

        // Create the tree structure from the data
        const root = d3.hierarchy(treeData);
        treeLayout(root);

        // Create the links (edges)
        svg.selectAll(".link")
            .data(root.links())
            .enter()
            .append("line")
            .attr("class", "link")
            .attr("x1", d => d.source.x + 50)
            .attr("y1", d => d.source.y + 50)
            .attr("x2", d => d.target.x + 50)
            .attr("y2", d => d.target.y + 50);

        // Create the nodes (elements)
        const nodes = svg.selectAll(".node")
            .data(root.descendants())
            .enter()
            .append("circle")
            .attr("class", "node")
            .attr("cx", d => d.x + 50)
            .attr("cy", d => d.y + 50)
            .attr("r", 20)
            .on("click", function(event, d) {
                handleNodeClick(d);
            });

        // Add labels to nodes
        svg.selectAll(".label")
            .data(root.descendants())
            .enter()
            .append("text")
            .attr("x", d => d.x + 50)
            .attr("y", d => d.y + 50)
            .attr("dy", 5)
            .attr("text-anchor", "middle")
            .text(d => d.data.name);

        // Handle node click event
        function handleNodeClick(node) {
            const clickedNodeName = node.data.name;

            if (clickedNodeName === correctBFSSequence[userClickIndex]) {
                // Correct click
                d3.select(event.target)
                    .classed("clicked", true);
                userClickIndex++;
                if (userClickIndex === correctBFSSequence.length) {
                    showMessage("成功，BFS遍历顺序正确！");
                }
            } else {
                // Incorrect click
                d3.select(event.target)
                    .classed("error", true);
                showMessage("错误，请重新开始！");
            }
        }

        // Display message
        function showMessage(message) {
            document.getElementById("message").innerText = message;
        }
    </script>
</body>
</html>
